package com.TheEndWork.thirdDay;

import java.util.*;

/**
 * @authoer zsj
 * @date 2022/5/25 12:55
 */
public class alg {

    public static void main(String[] args) {
        lanQiao600();
    }

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     *
     * @param nums 传入数组
     *             10203
     */
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index] = nums[i];
                index++;
            }
        }
        //12303
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }


    /**
     * 给你一个下标从 1 开始的整数数组numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
     * <p>
     * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
     * <p>
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     */
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
            }
        }
        return result;
    }


    /**
     * gcd(a,b) = gcd(b,a mod b)
     * 如果一个分数的分子和分母的最大公约数是 1这个分数称为既约分数。
     * 请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1和 2020）？
     */
    public static void lanQiao593() {
        int count = 0;
        for (int i = 1; i < 2021; i++) {
            for (int j = 1; j < 2021; j++) {
                if (gcd(i, j) == 1) {
                    count += 1;
                }
            }
        }
        System.out.println(count);
    }

    /**
     * 求最大公约数的方法
     *
     * @param n 数字1
     * @param m 数字2
     * @return 返回两个数字的最大公约数
     */
    public static int gcd(int n, int m) {
        if (m == 0) {
            return n;
        }
        return gcd(m, n % m);
    }


    /**
     * 小蓝有一个超大的仓库，可以摆放很多货物。
     * 现在，小蓝有 nn 箱货物要摆放在仓库，每箱货物都是规则的正方体。
     * 小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
     * 小蓝希望所有的货物最终摆成一个大的长方体。
     * 即在长、宽、高的方向上分别堆 LL、WW、HH 的货物,满足 n = L \times W \times Hn=L×W×H。
     * 给定 n，请问有多少种堆放货物的方案满足要求。
     * 例如，当 n=4 时，
     * 以下 66 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 11×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
     * 请问，当 n = 2021041820210418（注意有 16位数字）时，总共有多少种方案？
     */
    public static void lanQiao1463() {
        //求出这个数字的所有因子放入list集合中
        long n = 2021041820210418L;
        int count = 0;
        List<Long> list = new ArrayList<>();
        for (long i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                //如果属于它的因子
                list.add(i);
                //根据当前因子求出另一个因子，且要求两个因子不能相同
                long temp = n / i;
                if (temp != i) {
                    list.add(temp);
                }
            }
        }
        for (Long a : list) {
            for (Long b : list) {
                for (Long c : list) {
                    if (a * b * c == n) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }


    /**
     * 给定数列 1, 1, 1, 3, 5, 9, 17,从第 4 项开始，每项都是前 3 项的和
     * 求第 20190324 项的最后 4 位数字。
     */
    public static void lanQiao600() {
        int[] arr = new int[20190324];
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i < 20190324; i++) {
            arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
            arr[i] %= 10000;
        }
        System.out.println(arr[20190323]);
    }

    /**
     * 双指针经典题目
     * 一共有序数组nums,原地删除重复出现的元素，使每一个元素只出现一次
     * 返回删除数组元素之后的新长度
     * 不能使用额外空间 要求空间复杂度O(1)
     *
     * @param num 传入数组
     * @return 返回新数组长度
     */
    public static int removeRepeatValue(int[] num) {
        if (num == null) {
            throw new RuntimeException("空数组异常");
        }
        if (num.length == 0) {
            return 0;
        }
        int i = 0;
        for (int j = 0; j < num.length; j++) {
            if (num[i] != num[j]) {
                //如果两个数字不相同的话
                i++;
                num[i] = num[j];
            }
        }
        return i;
    }


    /**
     * 寻找数组的中心下标
     * 给你一个整数数组nums ，请计算数组的 中心下标 。
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     */
    public int pivotIndex(int[] nums) {
        int total = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (total == sum) {
                return i;
            }
            sum -= nums[i];
        }
        return -1;
    }

    /**
     * 给你一个非负整数 x ，计算并返回x的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     */
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }


    /**
     * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
     *
     * 其实就是比较
     * 最小的两个值*最大的那个值  ?  最大的三个值
     * 比较这两个值谁大
     */
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length-1;
        return Math.max(nums[0] * nums[1] * nums[n-1], nums[n] * nums[n - 1] * nums[n - 2]);
    }


    /**
     * dfs经典迷宫问题
     */
    public void dfs(){
        //dfs问题，基本上都是有一个标记数组去进行访问点的标记
        //然后不断往后退，也就是回溯
        //直到完全没有路可以走之后，返回想要的结果
        //bfs问题，就是有一个队列来记录进出的过程
    }

    /**
     * 把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以s 看起来是这样的：
     * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."
     * 现在给定另一个字符串 p 。返回s 中唯一 的 p 的 非空子串的数量。
     * @param p 传入字符
     * @return 返回结果
     *
     * 思路：
     * 先得到p的所有字串，暴力匹配在s中是否包含此子串   超时
     *
     * 动态规划dp数组  todo
     */
    public int findSubstringInWraproundString(String p) {
        if (p.length() == 1) return 1;
        int count = 0;
        Set<String> set = new HashSet<>();
        int n = p.length();
        char[] chars = p.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index =1;
            while (index < chars.length){
                set.add(chars[i]+chars[index]+"");
                index++;
            }
        }
       return set.size();
    }

}
